import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-28
 * Time: 10:20
 */

public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] ans = new int[numCourses];
        // 各节点的入度
        int[] inDegrees = new int[numCourses];
        ArrayList<ArrayList<Integer>> adjacencyList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjacencyList.add(new ArrayList<>());
        }
        // 创建邻接表
        for (int[] pre: prerequisites) {
            inDegrees[pre[0]]++;
            adjacencyList.get(pre[1]).add(pre[0]);
        }
        Queue<Integer> queue = new LinkedList<>();
        // 将入度为 0 的, 即没有先修课程的课, 即随时可以上的课加到队列
        for (int i = 0; i < inDegrees.length; i++) {
            if (inDegrees[i] == 0){
                queue.add(i);
            }
        }
        int count = 0;
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            // 修了这门课
            ans[count] = cur;
            count++;
            // 将以这门课为先修课程的课程的入度均 -1
            for (int to: adjacencyList.get(cur)) {
                inDegrees[to]--;
                // 没有先修课程了, 就加入到队列中
                if (inDegrees[to] == 0){
                    queue.add(to);
                }
            }
        }
        if (count != numCourses){
            return new int[0];
        }
        return ans;
    }
}
